import java.util.ArrayDeque;

/**
 * @author mubei
 * @date 2021/12/10
 * @description
 */
public class Demo01 {

    public static void main(String[] args) {
        int[] sequence = {1,2};
        if(sequence.length<=0){
            System.out.println(false);
        }
        System.out.println(VerifySquenceOfBST(sequence, 0, sequence.length));
    }

    public static boolean VerifySquenceOfBST(int [] sequence,int l,int r) {
        int root = sequence[r-1];
        int index = l;
        for (;index < r-1;index++){
            if(sequence[index] > root){
                break;
            }
        }
        int j = index;
        for (; j < r-1;j++){
            if(sequence[j] < root){
                return false;
            }
        }
        boolean left = true;
        if(index > l){
            left = VerifySquenceOfBST(sequence,l,index);
        }
        boolean right = true;
        // 一直是右子树
        if(index < r - 1){
            if(index == l){
                right = VerifySquenceOfBST(sequence,l,r-1);
            }else{
                right = VerifySquenceOfBST(sequence,index-1,r-1);
            }

        }
        return (left && right);
    }
}
